%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% data section
\SetKwData{MyCutOff}{cutoff}
%%
%% input
\KwIn{Positive integer $n$ and probability $0 < p < 1$.}
%%
%% output
\KwOut{A random oriented graph on $n$ vertices.}
\BlankLine
%%
%% algorithm body
$G \assign$ random graph in $G(n,p)$ as per Algorithm~\ref{alg:random_graphs:linear_generate_random_sparse_Gnp}\;
$E \assign$ edge set of $G$\;
$G \assign$ directed version of $G$\;
$\MyCutOff \assign$ draw uniformly at random from interval $(0,1)$\;
\For{\rm each edge $uv \in E$}{
  $r \assign$ draw uniformly at random from interval $(0,1)$\;
  \If{$r < \MyCutOff$}{
    remove $uv$ from $G$\;
  }
  \Else{
    remove $vu$ from $G$\;
  }
}
\Return $G$\;
